class Solution(object):
    def minCost(self, grid):
        cost = 0
        m = len(grid)
        n = len(grid[0])
        st = {(0, 0)}
        already = {(0, 0)}
        x, y = 0, 0
        while True:
            if grid[x][y] == 1:
                ux, uy = x, y + 1
            if grid[x][y] == 2:
                ux, uy = x, y - 1
            if grid[x][y] == 3:
                ux, uy = x + 1, y
            if grid[x][y] == 4:
                ux, uy = x - 1, y
            if 0 <= ux < m and 0 <= uy < n and (ux, uy) not in already:
                st.add((ux, uy))
                already.add((ux, uy))
                x, y = ux, uy
            else:
                break
        if (m - 1, n - 1) in already:
            return 0
        while st:
            cost += 1
            next_st = set()
            for x, y in st:
                for k in range(3):
                    direction = (grid[x][y] + k) % 4 + 1
                    if direction == 1:
                        ux, uy = x, y + 1
                    if direction == 2:
                        ux, uy = x, y - 1
                    if direction == 3:
                        ux, uy = x + 1, y
                    if direction == 4:
                        ux, uy = x - 1, y
                    if 0 <= ux < m and 0 <= uy < n and (ux, uy) not in already:
                        if (ux, uy) == (m - 1, n - 1):
                            return cost
                        next_st.add((ux, uy))
                        already.add((ux, uy))
                        tx, ty = ux, uy
                        while True:
                            if grid[tx][ty] == 1:
                                ux, uy = tx, ty + 1
                            if grid[tx][ty] == 2:
                                ux, uy = tx, ty - 1
                            if grid[tx][ty] == 3:
                                ux, uy = tx + 1, ty
                            if grid[tx][ty] == 4:
                                ux, uy = tx - 1, ty
                            if 0 <= ux < m and 0 <= uy < n and (ux, uy) not in already:
                                if (ux, uy) == (m - 1, n - 1):
                                    return cost
                                next_st.add((ux, uy))
                                already.add((ux, uy))
                                tx, ty = ux, uy
                            else:
                                break
            st = next_st


data = Solution()
grid = [[3,4,3],[2,2,2],[2,1,1]]
print(data.minCost(grid))
# grid = [[1, 1, 1, 1], [2, 2, 2, 2], [1, 1, 1, 1], [2, 2, 2, 2]]
# print(data.minCost(grid))
